<?php

namespace Pro\Support;

/**
 * 区间查询检查器 - 详细注释版
 *
 * 功能：查询指定区间[a,b]与数据库中区间的重叠情况，返回详细的分段结果
 *
 * 算法核心思想（关键点收集法）：
 * 1. 收集所有关键点（区间边界点）
 * 2. 基于关键点创建不重叠的子区间
 * 3. 为每个子区间确定对应的状态
 *
 * 算法示例：
 * 数据库数据：[1,4]作废, [5,20]正常, [30,40]作废
 * 查询区间：[3, 43]
 *
 * 步骤1：查询重叠区间 → [1,4], [5,20], [30,40]
 * 步骤2：收集关键点 → [3, 5, 21, 30, 41, 44]
 * 步骤3：创建子区间 → [3,4], [5,20], [21,29], [30,40], [41,43]
 * 步骤4：确定状态 → 作废, 正常, 不存在, 作废, 不存在
 *
 * 时间复杂度：O(log n + k) 其中n是表中区间数，k是重叠区间数
 * 空间复杂度：O(k) 只存储重叠的区间
 */
class IntervalChecker
{
    /**
     * 检查区间[a, b]在表中的存在情况
     *
     * 算法步骤：
     * 1. 收集所有关键点（区间边界点）
     * 2. 基于关键点创建不重叠的子区间
     * 3. 为每个子区间确定对应的状态
     *
     * @param array $overlapping 待检查的区间数组
     * @param int $startNum 查询区间起始值
     * @param int $endNum 查询区间结束值
     * @return array 包含各子区间及其状态的数组
     */
    public static function checkInterval(array $overlapping, int $startNum, int $endNum): array
    {
        //如果区间为空，则返回异常结果
        if (empty($overlapping)) {
            return [
                [
                    'start' => $startNum,
                    'end' => $endNum,
                    'check_state' => '异常',
                    'exists' => false
                ],
            ];
        }

        // 步骤1：收集所有关键点（区间边界点）
        $points = [
            $startNum,   // 查询区间的开始点
            $endNum + 1  // 查询区间的结束点+1（+1是为了确保最后一个点被包含）
        ];

        // 遍历所有重叠的数据库区间，收集它们的边界点
        foreach ($overlapping as $interval) {
            // 计算与查询区间重叠的部分
            $start = max($interval['serial_num_start'], $startNum);  // 重叠部分的开始点
            $end = min($interval['serial_num_end'], $endNum);      // 重叠部分的结束点

            // 只有当重叠部分有效时才添加边界点
            if ($start <= $end) {
                $points[] = $start;      // 重叠部分的开始点
                $points[] = $end + 1;    // 重叠部分的结束点+1
            }
        }

        // 步骤2：去重并排序关键点
        $points = array_unique($points);  // 去除重复的点
        sort($points);                    // 按从小到大的顺序排序

        $result = [];

        // 步骤3：基于关键点创建子区间
        for ($i = 0; $i < count($points) - 1; $i++) {
            // 当前子区间的开始和结束点
            $segmentStart = $points[$i];        // 当前关键点
            $segmentEnd = $points[$i + 1] - 1;  // 下一个关键点-1

            // 确保子区间在查询范围内
            if ($segmentStart > $endNum || $segmentEnd < $startNum) {
                continue;  // 跳过超出查询范围的子区间
            }

            // 进一步确保子区间在查询范围内
            $segmentStart = max($segmentStart, $startNum);
            $segmentEnd = min($segmentEnd, $endNum);

            // 只有当子区间有效时才处理
            if ($segmentStart <= $segmentEnd) {
                // 查找覆盖此子区间的数据库区间
                $coveringInterval = self::findCoveringInterval($overlapping, $segmentStart, $segmentEnd);
                if ($coveringInterval) {
                    // 如果找到覆盖的数据库区间，使用其状态
                    $result[] = [
                        'start' => $segmentStart,
                        'end' => $segmentEnd,
                        'check_state' => $coveringInterval['check_state'],
                        'exists' => true
                    ];
                } else {
                    // 如果没有找到覆盖的数据库区间，标记为不存在
                    $result[] = [
                        'start' => $segmentStart,
                        'end' => $segmentEnd,
                        'check_state' => '异常',
                        'exists' => false
                    ];
                }
            }
        }

        return $result;
    }

    /**
     * 查找覆盖指定子区间的数据库区间
     *
     * 判断条件：数据库区间的开始位置 <= 子区间开始位置 且 数据库区间的结束位置 >= 子区间结束位置
     * 即：数据库区间完全包含子区间
     *
     * @param array $intervals 数据库区间数组
     * @param int $start 子区间开始位置
     * @param int $end 子区间结束位置
     * @return array 覆盖的区间
     */
    private static function findCoveringInterval(array $intervals, int $start, int $end): array
    {
        // 遍历所有数据库区间
        foreach ($intervals as $interval) {
            // 检查数据库区间是否完全包含子区间
            // 条件：数据库区间的开始 <= 子区间开始 且 数据库区间的结束 >= 子区间结束
            if ($interval['serial_num_start'] <= $start && $interval['serial_num_end'] >= $end) {
                return $interval;  // 找到覆盖的区间，返回它
            }
        }
        return [];  // 没有找到覆盖的区间
    }
}

/*$overlapping = [
    [
        'serial_num_start' => 1,
        'serial_num_end' => 4,
        'check_state' => '作废',
    ],
    [
        'serial_num_start' => 6,
        'serial_num_end' => 20,
        'check_state' => '正常',
    ],
    [
        'serial_num_start' => 30,
        'serial_num_end' => 40,
        'check_state' => '作废',
    ],
];

$result = IntervalChecker::checkInterval($overlapping, 1, 43);
print_r($result);*/
